package algorithms.nqueen;

/**
 * N皇后问题:
 *
 * 回溯算法的基本思想
 * 试探：尝试构造问题的解。
 * 回退：当发现当前的选择不能达到有效的解时，就撤销最近的选择，回到上一步重新选择。
 * 剪枝：通过设置约束条件来提前排除不满足条件的分支，以减少搜索的空间。
 */
public class QueenN {
    static int count = 0;

    public static void main(String[] args) {
        int[] cols = new int[8];// 放置皇后的棋盘,下标表示列(col),数值表示行(row)
        find(cols, 0);// 从第0行开始放置
        System.out.println("解的数量=>"+count);
    }

    /**
     *
     * @param cols : 棋盘
     * @param row : 行号
     */
    public static void find(int cols[], int row) {
        if (row == cols.length) {
            count++;
            // ok
            System.out.println("--------------------start------------------------");
            printQ(cols);
            System.out.println("--------------------end------------------------");
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            // 满足就在该位置放置皇后,进行下一步检查
            if (valid(cols, row, col)) {
                cols[row] = col;
                find(cols, row + 1);
            }
        }

    }

    private static void printQ(int[] cols) {
        for (int i = 0; i < cols.length; i++) {
            StringBuffer stringBuffer = new StringBuffer("[");
            for (int j = 0; j < cols.length; j++) {
                if (cols[i] == j) {
                    stringBuffer.append("1");
                } else {
                    stringBuffer.append("0");
                }
                if (j < cols.length - 1) {
                    stringBuffer.append(",");
                }
            }
            stringBuffer.append("]");
            System.out.println(stringBuffer.toString());
        }
    }

    /**
     * @param row : 行
     * @param col : 列
     * @return
     */
    private static boolean valid(int cols[], int row, int col) {
        for (int i = 0; i < row; i++) {
            // 检查是否在同一列或同一对角线
            // 同一对角线 等价于 行列互减的绝对值相等  [1,2],[2,1] ,|1-2| == |2-1|;
            if (cols[i] == col || Math.abs(cols[i] - col) == row - i) {
                return false;
            }
        }
        return true;
    }
}
